package code201_300.code80_90;

/**
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 * 输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 *
 * 必须在原数组上操作，不能拷贝额外的数组。
 * 尽量减少操作次数。
 */
public class _283moveZeros {

    /**
     * 思考：参考冒泡排序了，双指针，记录并交换。
     *
     * 2:第二种方案：遍历两次即可，第一次将所有非零元素全部赋值到1-n，第二次遍历把n之后的全部赋值为0即可
     *
     * 执行用时：     * 2 ms     * , 在所有 Java 提交中击败了     * 48.94%     * 的用户
     * 内存消耗：     * 39.4 MB     * , 在所有 Java 提交中击败了     * 69.01%     * 的用户
     * @param nums
     */
    public static void moveZeroes0(int[] nums) {
        if(nums.length==0||nums.length==1)return;
        // 下一个0的下标
        int k = 0;
        boolean flag = false;
        // 要和当前0交换的数的下标
        int l = 0;
        while (l!=nums.length){
            // 找到第一个需要交换的0
            if(nums[k]!=0){
                k++;
            }else {
                flag = true;
            }
            // 找到第一个需要交换的非0
            if(nums[l]!=0&&flag){
                int temp = nums[k];
                nums[k] = nums[l];
                nums[l] = temp;
            }
            l++;
        }
    }

    public static void main(String[] args) {
        moveZeroes(new int[]{1,0});
    }

    /**
     * 题解代码思路清晰，易读
     * 执行用时：     * 2 ms     * , 在所有 Java 提交中击败了     * 48.94%     * 的用户
     * 内存消耗：     * 39.4 MB     * , 在所有 Java 提交中击败了     * 69.42%     * 的用户
     * @param nums
     */
    public static void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

}
